package com.sicheng.lc.lc笔试.腾讯篇;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/8 21:56
 */
public class 字符串操作 {
    /**
     * 给定一个只包含小写字母字符串，每次可以选择两个相同的字符删除，并在字符串结尾新增任意一个小写字母。
     * 请问最少多少次操作后，所有的字母都不相同？
     * 字符串长度<1e3
     * <p>
     * input:
     * abab
     * <p>
     * output:
     * 2
     * 第一次把2个a变成f，第二次把2个b变成b。得到fb，每个字母都不相同，最少操作次数为2。
     */
    long cnt(String s) {
        int[] chars = new int[26];
        for (int i = 0; i < s.length(); i++) {
            chars[s.charAt(i) - 'a']++;
        }
        long res = 0;
        long empty = 0;
        long out = 0;

        //  a~z 思路不好想
        //  首先统计字符串的词频 chars
        //  每个字符多出的部分抵消掉，字符最后会变成 0/1 , 同时会产出 sum(chars[i]/2) 个字符
        //  先把产出放一边不管 统计剩余的空位
        //  产出字符 先塞到空位里这是不需要花费代价的
        //  如果还有产出 那么这些产出 就会产生额外的代价 逻辑上看做是和某个字符不断抵消再生成抵消的字符
        //  复杂度分析 O(N)
        //   举个小例子 a~y 都出现3次 z出现0次 产出25(25次代价已经花了)个字符 然后 a~y都是1 有一个空位z 填补1个z(这是不需要花费代价)
        //   还剩余 25 - 1 =24 的产出  看成都和a抵消又产出a 需要额外的代价 所以总代价是 25+24
        //   还有一种复杂度偏高的思路就是抵消2个字符产出最小词频的字符，直到所有字符的词频都变成1
        for (int i = 0; i < chars.length; i++) {
            out += chars[i] >> 1;
            res += chars[i] >> 1;
            chars[i] &= 1;
            empty += 1 - chars[i];
        }
        // 塞到空位里
        out -= Math.min(empty, out);

        return res + out;
    }
}
